

#ifndef ALLOCATORHEAPBASED_H
#define	ALLOCATORHEAPBASED_H

#include "Debugging.h"

#include <boost/scoped_ptr.hpp>
using boost::scoped_ptr;
#include <boost/assert.hpp>


#define ALLIGNUP(address,alignment) ((void*)((((unsigned int)(address))  +  (alignment) -1 ) & (~((alignment)-1)) ))


#define ALLIGN_UP_AFTER_BLOCK(address,alignment,blockSize)\
((void*)(  ((unsigned int)(ALLIGNUP((((unsigned int)(address) ) + ((unsigned int)(blockSize) )),(alignment)    )))-((unsigned int)(blockSize) ))   )


class AllocatorHeapBased
{
public:

    struct BlockDescriptor
    {
        enum
        {
            BLOCK_DESCRIPTOR_HEADER=1017
        };

        BlockDescriptor(BlockDescriptor* _prev, BlockDescriptor* _next, bool _free, size_t _size)
                :prev(_prev), next(_next), free(_free), size(_size)
        {
            ONLY_WHEN_DEBUGGING(BlockDescriptorHeader=BLOCK_DESCRIPTOR_HEADER;)
        };

        ~BlockDescriptor()
        {
            free=true;
            ONLY_WHEN_DEBUGGING(BlockDescriptorHeader=0;)
        }

        ONLY_WHEN_DEBUGGING(int BlockDescriptorHeader;)
        BlockDescriptor* prev;
        BlockDescriptor* next;
        bool free;
        size_t size;

    } ;

    class bad_deallocation: public std::exception
    {
        public:
        bad_deallocation(const char *what):what_(what){}
            const char* what(){return what_;}
        private:
            const char *what_;
    };


    AllocatorHeapBased(size_t _MaxTotalDataSize,size_t _MaxAmountOfDataChunks,unsigned int _byteAlignment=16)
    :byteAlignment(_byteAlignment)
    {
        heapSize=_byteAlignment+_MaxTotalDataSize+_MaxAmountOfDataChunks*(sizeof(BlockDescriptor)+_byteAlignment)+2*_byteAlignment;

        heap.reset(new char[heapSize]);
        firstBlockDescriptor=(BlockDescriptor*)(ALLIGN_UP_AFTER_BLOCK((void *)heap.get(),_byteAlignment,sizeof(BlockDescriptor)));
        ::new((void*)firstBlockDescriptor) BlockDescriptor(NULL, NULL, true,heapSize-sizeof(BlockDescriptor)-_byteAlignment );

        
    }

    void* allocate(size_t size)
    {


        BlockDescriptor* block=firstBlockDescriptor;

        while(!( (block==NULL) || ((block->free) &&  (block->size>=size))  ))
        {
            block=block->next;
        }

        if(block==NULL)
            throw std::bad_alloc();

        if(block->size-size>=sizeof(BlockDescriptor)+2*byteAlignment)
        {
            BlockDescriptor* newBlock=(BlockDescriptor *)ALLIGN_UP_AFTER_BLOCK( ((char*)block+sizeof(BlockDescriptor)+size),byteAlignment,sizeof(BlockDescriptor));

            ::new((void *)newBlock) BlockDescriptor(block, block->next, true,
            (((char*)block)+sizeof(BlockDescriptor)+block->size)-(((char*)newBlock)+sizeof(BlockDescriptor)) );

            if(newBlock->next)newBlock->next->prev=newBlock;
            block->next=newBlock;
            block->size=((char*)newBlock)-(((char*)block)+sizeof(BlockDescriptor));
        }

        block->free=false;

        return (void*)(((char*)block)+sizeof(BlockDescriptor));

    }

    void deallocate(void *p, size_t = 0)
    {
        if(p==NULL)throw bad_deallocation("NULL pointer");

        BlockDescriptor* b= (BlockDescriptor*)(  ((char*)(p))-sizeof(BlockDescriptor)   );

        ONLY_WHEN_DEBUGGING(  \
                if(  b->BlockDescriptorHeader!=BlockDescriptor::BLOCK_DESCRIPTOR_HEADER )\
                    throw bad_deallocation("");
            ;)
 
        if(b->free)throw bad_deallocation("already free");



        if(b->prev && b->next && b->prev->free && b->next->free)
        {
            b->prev->size += b->size + b->next->size + 2*sizeof(BlockDescriptor);
            b->prev->next = b->next->next;
            if(b->next->next)b->next->next->prev = b->prev;
            b->~BlockDescriptor();
            return;
        }
        else if(b->prev&& b->prev->free)
        {
            b->prev->size += b->size + sizeof(BlockDescriptor);
            b->prev->next=b->next;
            if(b->next) b->next->prev = b->prev;
            b->~BlockDescriptor();
            return;
        }
        else if(b->next&&b->next->free)
        {
            BlockDescriptor* b_next=b->next;

            b->size += b->next->size + sizeof(BlockDescriptor);
            b->next = b->next->next;
            if(b->next) b->next->prev = b;
            b->free= true;

            b_next->~BlockDescriptor();

            return;
        }

        b->free = true;



    }

private:
    AllocatorHeapBased(AllocatorHeapBased&);
    AllocatorHeapBased& operator=(AllocatorHeapBased&);


    

    const unsigned int byteAlignment;
    size_t heapSize;
    scoped_ptr<char> heap;
    BlockDescriptor* firstBlockDescriptor;
};





#endif	/* ALLOCATORHEAPBASED_H */

